package com.dubious.interview.euler;

import java.math.BigInteger;
import java.util.List;

public class Problem113 {

    /**
     * Working from left-to-right if no digit is exceeded by the digit to its left it is called 
     * an increasing number; for example, 134468.
     * 
     * Similarly if no digit is exceeded by the digit to its right it is called a decreasing 
     * number; for example, 66420.
     * 
     * We shall call a positive integer that is neither increasing nor decreasing a "bouncy" 
     * number; for example, 155349.
     * 
     * As n increases, the proportion of bouncy numbers below n increases such that there are only 
     * 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers 
     * below 10^10.
     * 
     * How many numbers below a googol (10^100) are not bouncy?
     */
    public static long run(int exponent)
    {
        // strategy: mathematics
        
        // calculating the decreasing numbers:
        // - doing some work by hand this seems related to pascal's triangle
        // for an exponent of 5, for instance, (4-digit numbers), we calculate the
        // number of decreasing numbers as follows:
        // 3c3*10 + 4c3*9 + 5c3*8 + 6c3*7 + ... + 12c3*1 - 1
    
        long decreasingCount = 0;
        // we start at 2-digit numbers because 1-digit numbers will all be considered "increasing", anyway,
        // and they would give some weird divisions by 0 here.
        for(int i = 2; i <= exponent; i++)
        {
            for(int j = 10; j >= 1; j--)
            {
                decreasingCount += j * getBinomialCoefficient(i - 2 + 10 - j, i - 2);
            }
            
            // consider that 9 of these numbers will also be increasing
            // consider that 1 of these numbers will be 0
            decreasingCount -= 10;
        }
        System.out.println("decreasing: " + decreasingCount);
        
        // the set of increasing numbers are calculated differently, we just need to apply
        // a similar pattern, once, for the exponent.
        
        long increasingCount = 0;
        for(int j = 10; j >= 1; j--)
        {
            increasingCount += j * getBinomialCoefficient(exponent - 2 + 10 - j, exponent - 2);
        }
        // consider that 1 of these numbers will be 0
        increasingCount -= 1;
        
        System.out.println("increasing: " + increasingCount);
        
        return increasingCount + decreasingCount;
    }
    
    private static long getBinomialCoefficient(int top, int bottom)
    {
        // these factorials will return some big numbers so we use BigInteger
        return factorial(top).divide(factorial(bottom).multiply(factorial(top - bottom))).longValue();
    }
    
    private static BigInteger factorial(int n)
    {
        BigInteger factorial = BigInteger.ONE;
        for(int i = 2; i <= n; i++)
        {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }
        
        return factorial;
    }
    
    public static long run2(int exponent)
    {
        // strategy: brute-force 
        // iterate over all numbers and determine how many are non-bouncy
        long upperBound = (long)Math.pow(10, exponent);
        int nonBouncyCount = 0;
        
        for(int i = 1; i < upperBound; i++)
        {
            List<Integer> digits = Utilities.extractDigits(i);
            if(Utilities.isIncreasing(digits) || Utilities.isDecreasing(digits))
            {
                nonBouncyCount++;
            }
        }
        
        return nonBouncyCount;
    }
}
